package code1.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 原题链接：https://leetcode.cn/problems/n-queens/
 */
public class P51 {

    int[] a=new int[12];             //a[i]表示第i行的皇后放在第几列
    boolean[] b=new boolean[100];     //b[i]表示第i列时候可以放
    boolean[] c=new boolean[100];     //c[i]表示对应的副对角线上是否可以放
    boolean[] d=new boolean[100];     //d[i]表示对应的主对角线上是否可以放

    List<List<String>> res=new ArrayList<>();       //返回结果集

    public void dfs(int i,int n){      //i表示第几层
        if(i>n){
            //打印当前棋盘
            print(n);
            return;
        }
        for(int j=1;j<=n;j++){
            if(b[j] && c[i+j] && d[i-j+n]){     //满足落子条件
                a[i]=j;                 //落子
                b[j]=false;
                c[i+j]=false;
                d[i-j+n]=false;
                dfs(i+1,n);
                b[j]=true;         //回溯
                c[i+j]=true;
                d[i-j+n]=true;
            }
        }
    }

    public void print(int n) {
        List<String> list=new ArrayList<>();
        for(int i=1;i<=n;i++){
            StringBuilder sb=new StringBuilder();
            for(int j=1;j<=n;j++){
                if(j==a[i]){
                    sb.append('Q');
                }else{
                    sb.append('.');
                }
            }
            list.add(sb.toString());
        }
        res.add(list);
    }

    public List<List<String>> solveNQueens(int n) {
        Arrays.fill(b,true);            //初始化为true，不然默认为false
        Arrays.fill(c,true);
        Arrays.fill(d,true);
        dfs(1,n);
        return res;
    }

}
